|
In computational geometry, The opaque forest problem can be stated as follows: "''Given a convex polygon ''C'' in the plane, determine the minimal forest ''T'' of closed, bounded line segments such that every line through ''C'' also intersects ''T". ''T'' is said to be the ''opaque forest'', or ''barrier'' of ''C''. ''C'' is said to be the ''coverage'' of ''T''. While any forest that covers ''C'' is a barrier of ''C'', we wish to find the one with shortest length. It may be the case that ''T'' is constrained to be strictly interior or exterior to ''C''. In this case, we specifically refer to a barrier as ''interior'' or ''exterior''. Otherwise, the barrier is assumed to have no constraints on its location. == History and difficulty == The opaque forest problem was originally introduced by Mazurkiewicz in 1916. 〔S. Mazurkiewicz, Sur un ensemble ferm´e, punctiforme, qui rencontre toute droite passant par un certain domaine (Polish, French summary), Prace Mat.-Fiz. 27 (1916), 11–16.〕 Since then, not much progress has been made with respect to the original problem. There does not exist ''any'' verified general solution to the problem. In fact, the optimal solution for even simple fixed inputs such as the unit square or equilateral triangle are unknown. There exist conjectured optimal solutions to both of these instances, but we currently lack the tooling to prove that they are optimal.〔Opaque sets; Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques; 194–205〕 While general solutions to the problem have been claimed by several individuals,〔V. Akman, An algorithm for determining an opaque minimal forest of a convex polygon, Information Processing Letters, 24 (1987), 193–198.〕〔P. Dublish, An O(''n''3) algorithm for finding the minimal opaque forest of a convex polygon, Information Processing Letters, 29(5) (1988), 275–276.〕 they either haven't been peer reviewed or have been demonstrated to be incorrect.〔T. Shermer, A counterexample to the algorithms for determining opaque minimal forests, Information Processing Letters, 40 (1991), 41–42.〕〔J. S. Provan, M. Brazil, D. A. Thomas and J. F. Weng, Minimum opaque covers for polygonal regions, manuscript, October 2012, arXiv:1210.8139v1〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Opaque forest problem」の詳細全文を読む スポンサード リンク
|